package com.lhcai.nk;

import java.util.Stack;

/**
 * @author lhcstart
 * @create 2023-02-23 23:02
 */

/**
 * 描述
 * 给定一个字符串s，字符串s只包含以下三种字符: (，*，)，请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
 * 1.左括号'('必须有对应的右括号')'
 * 2.右括号')'必须有对应的左括号'('
 * 3.左括号必须在对应的右括号前面
 * 4.*可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符
 * 5.空字符串也视为合法的括号字符串
 * 数据范围:1<=s.length<=100
 */
public class NC175 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValidString(String s) {
        // write code here
        Stack<Integer> left = new Stack<>();
        Stack<Integer> star = new Stack<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            if (ch == '(') {
                left.push(i);
            } else if (ch == '*') {
                star.push(i);
            } else {
                if (!left.isEmpty()) {
                    left.pop();
                } else if (!star.isEmpty()) {
                    star.pop();
                } else {
                    return false;
                }
            }
        }
        while (!left.isEmpty() && !star.isEmpty()) {
            Integer p1 = left.pop();
            Integer p2 = star.pop();
            if (p1 > p2) {
                return false;
            }
        }
        return left.isEmpty();
    }

    public static boolean isValidString2(String s) {
        // write code here
        int mincount = 0;//待消除左括号的最小个数
        int maxcount = 0;//待消除左括号的最大个数
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                mincount++;
                maxcount++;
            } else if (s.charAt(i) == ')') {
                mincount = Math.max(mincount - 1, 0);
                maxcount--;
                if (maxcount < 0) {
                    return false;
                }
            } else {
                mincount = Math.max(mincount - 1, 0);
                maxcount++;
            }
        }
        return mincount == 0;
    }
}
